"""
详细描述
将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。

例如: n = 7, k = 3, 下面三种分法被认为是相同的：

1, 1, 5; 1, 5, 1; 5, 1, 1。

问有多少种不同的分法。

输入: n, k (6 < n < 200, 1 < k < 7)

输出: 一个整数 (所有可能的分法总数)
"""
#
# Note: 类名、方法名、参数名已经指定，请勿修改
#
#
#
# @param n int整型 整数n
# @param k int整型 分为k份
# @return int整型
#
class Solution:
    def divide(self, n, k):
        dp = [[0] * (k+1) for _ in range(n+1)]
        dp[0][0] = 1
        for i in range(1, n+1):
            for j in range(1, min(i, k)+1):
                dp[i][j] = dp[i-j][j]+dp[i-1][j-1]
        return dp[n][k]


if __name__ == '__main__':
    # n,k = 7, 3
    s = Solution()
    print(s.divide(7, 3))
    # dp = [[0] * (k + 1) for _ in range(n + 1)]
    # print(dp)
